Sort array by parity [Sort, Two Pass, In-place]

Time: O(N); Space: O(1); easy

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Example 1:

Input: A = [3,1,2,4]

Output: [2,4,3,1]

The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Note:

• 1 <= A.length <= 5000

• 0 <= A[i] <= 5000

1. Sort

Intuition and Algorithm Use a custom comparator when sorting, to sort by parity.

class Solution1(object):
    """
    Sort
    Time: O(NLogN), N is a length of A
    Spase: O(N)
    """
    def sortArrayByParity(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        A.sort(key = lambda x: x % 2)
        return A

s = Solution1()
A = [3,1,2,4]
assert s.sortArrayByParity(A) == [2,4,3,1] or [4,2,3,1] or [2,4,1,3] or [4,2,1,3]

2. Two Pass

Intuition and Algorithm Write all the even elements first, then write all the odd elements.

class Solution2(object):
    """
    Two Pass
    Time: O(N), N is a length of A
    Spase: O(N)
    """
    def sortArrayByParity(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        return ([x for x in A if x % 2 == 0] +
                [x for x in A if x % 2 == 1])

s = Solution2()
assert s.sortArrayByParity(A) == [2,4,3,1] or [4,2,3,1] or [2,4,1,3] or [4,2,1,3]

3. In-Place

Intuition If we want to do the sort in-place, we can use quicksort, a standard textbook algorithm.

Algorithm We’ll maintain two pointers i and j. The loop invariant is everything below i has parity 0 (ie. A[k] % 2 == 0 when k < i), and everything above j has parity 1.

Then, there are 4 cases for (A[i] % 2, A[j] % 2): * If it is (0, 1), then everything is correct: i++ and j–. * If it is (1, 0), we swap them so they are correct, then continue. * If it is (0, 0), only the i place is correct, so we i++ and continue. * If it is (1, 1), only the j place is correct, so we j– and continue.

Throughout all 4 cases, the loop invariant is maintained, and j-i is getting smaller. So eventually we will be done with the array sorted as desired.

class Solution3(object):
    """
    In-place
    Time: O(N), Each step of the while loop makes j-i decrease by at least one.
    (Note that while quicksort is O(NLogN) normally,
     this is O(N) because we only need one pass to sort the elements.)
    Spase: O(1)
    """
    def sortArrayByParity(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        i, j = 0, len(A) - 1
        while i < j:
            if A[i] % 2 > A[j] % 2:
                A[i], A[j] = A[j], A[i]

            if A[i] % 2 == 0: i += 1
            if A[j] % 2 == 1: j -= 1

        return A

s = Solution3()
assert s.sortArrayByParity(A) == [2,4,3,1] or [4,2,3,1] or [2,4,1,3] or [4,2,1,3]

class Solution4(object):
    """
    In-place
    Time:  O(N)
    Space: O(1)
    """
    def sortArrayByParity(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        i = 0
        for j in range(len(A)):
            if A[j] % 2 == 0:
                A[i], A[j] = A[j], A[i]
                i += 1
        return A

s = Solution4()
assert s.sortArrayByParity(A) == [2,4,3,1] or [4,2,3,1] or [2,4,1,3] or [4,2,1,3]

See also:

https://leetcode.com/problems/sort-array-by-parity

https://www.lintcode.com/problem/sort-array-by-parity